//
// Created by Administrator on 2021/4/7.
//

#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

//  Definition for a binary tree node.
// 树节点定义
struct TreeNode {
    int val; // 节点值
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
private:
    int post_idx{};
    unordered_map<int, int> idx_map;
public:
    //递归函数 in_left in_right 表示当前递归到中序序列中当前子树的左右边界
    TreeNode *helper(int in_left, int in_right, vector<int> &preorder, vector<int> &inorder) {
        // 如果这里没有节点构造二叉树了，就结束
        if (in_left > in_right) {
            return nullptr;
        }
        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = preorder[post_idx];
        auto *root = new TreeNode(root_val);
//        cout << root_val<<endl;
        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];
        // 下标加一
        post_idx++;
        // 构造左子树
        root->left = helper(in_left, index - 1, preorder, inorder);
        // 构造右子树
        root->right = helper(index + 1, in_right, preorder, inorder);
        return root;
    }

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // 从前序遍历的第一个元素开始
        post_idx = 0;
        // 建立（元素，下标）键值对的哈希表 高效查找根节点元素在中序遍历数组中的下标
        int idx = 0;
        for (auto &val : inorder) {
            idx_map[val] = idx++;
        }
        return helper(0, (int) inorder.size() - 1, preorder, inorder);
    }

    void preorder(TreeNode *t, vector<int> &v) { // 前序遍历 递归函数
        if (t == nullptr) {
            return;
        }
        v.push_back(t->val);
        preorder(t->left, v);
        preorder(t->right, v);
    }

    void inorder(TreeNode *t, vector<int> &v) { // 中序遍历 递归函数
        if (t == nullptr) {
            return;
        }
        inorder(t->left, v);
        v.push_back(t->val);
        inorder(t->right, v);
    }

    void postorder(TreeNode *t, vector<int> &v) { // 后序遍历 递归函数
        if (t == nullptr) {
            return;
        }
        postorder(t->left, v);
        postorder(t->right, v);
        v.push_back(t->val);
    }

    vector<int> preorderTraversal(TreeNode *root) { // 前序遍历 调用函数
        vector<int> ans;
        preorder(root, ans);
        return ans;
    }

    vector<int> inorderTraversal(TreeNode *root) { // 中序遍历 调用函数
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }

    vector<int> postorderTraversal(TreeNode *root) { // 后序遍历 调用函数
        vector<int> ans;
        postorder(root, ans);
        return ans;
    }


};


int main() {
//    前序遍历 preorder = [3,9,20,15,7]
//    中序遍历 inorder = [9,3,15,20,7]

    vector<int> pre{3,9,20,15,7};
    vector<int> in{9,3,15,20,7};
    Solution sol;
    auto t = sol.buildTree(pre, in);

    auto a = sol.preorderTraversal(t);
    cout << "preorder:" << endl;
    for (auto x:a) cout << x << endl;
    a = sol.inorderTraversal(t);
    cout << "inorder:" << endl;
    for (auto x:a) cout << x << endl;
    a = sol.postorderTraversal(t);
    cout << "postorder:" << endl;
    for (auto x:a) cout << x << endl;
}